package com.leetcode.partition1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/9/6 10:03
 */
public class LC56合并区间 {

    public static int[][] merge(int[][] intervals) {
        return greedy(intervals);
    }

    public static void main(String[] args) {
//        int[][] intervals = {{1, 4}, {0, 2}, {3, 5}};
        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
//        int[][] intervals = {{1, 4}, {2, 3}};
        System.out.println(Arrays.deepToString(merge(intervals)));
    }

    private static int[][] greedy(final int[][] intervals) {
        if (intervals.length == 0 || intervals.length == 1) return intervals;

        List<int[]> answerLists = new ArrayList<>();
        Arrays.sort(intervals, (o1, o2) -> o1[0] == o2[0] ? Integer.compare(o1[1], o2[1]) : Integer.compare(o1[0], o2[0]));
        for (int i = 1; i < intervals.length; i++) {
            int start = intervals[i - 1][0], end = intervals[i - 1][1];
            while (i < intervals.length && intervals[i][0] <= end) {        //寻找在范围内的最大右边界
                end = Math.max(end, intervals[i][1]);
                i++;
            }
            //将开始位置和能搜索到的最大位置加入结果
            answerLists.add(new int[]{start, end});
        }
        //检查是否将最后一个区间包含了进去
        if (answerLists.get(answerLists.size() - 1)[1] < intervals[intervals.length - 1][1]) {
            answerLists.add(intervals[intervals.length - 1]);
        }
        return answerLists.toArray(new int[answerLists.size()][]);
    }

    private static int[][] doubleIndex(final int[][] intervals) {
        List<int[]> answerLists = new ArrayList<>();
        List<Integer> startList = new ArrayList<>();
        List<Integer> endList = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            startList.add(intervals[i][0]);
            endList.add(intervals[i][1]);
        }
        startList.sort((o1, o2) -> Integer.compare(o1, o2));
        endList.sort((o1, o2) -> Integer.compare(o1, o2));
        for (int i = 0, j = 0; i < intervals.length; i++) {
            if (i == intervals.length - 1 || startList.get(i + 1) > endList.get(i)) {
                answerLists.add(new int[]{startList.get(j), endList.get(i)});
                j = i + 1;
            }
        }
        return answerLists.toArray(new int[answerLists.size()][]);
    }
}
